import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode {
}

//leetcode:46:quanpailie
class Solution1 {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums){
        if(nums.length == path.size()){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}

//leetcode:47:全排列II
class Solution2 {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        Arrays.sort(nums);
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    //只考虑合法qingk
    public void dfs(int[] nums){
        if(path.size() == nums.length){
            List<Integer> path_ = new ArrayList<>(path);
            ret.add(path_);
        }
        for(int i = 0;i < nums.length;i++){
            if(check[i] == false &&(i == 0 || nums[i] != nums[i-1] || check[i-1] == true)){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
    //只考虑不合法情况
    /*
    public void dfs(int[] nums){
        if(path.size() == nums.length){
            List<Integer> path_ = new ArrayList<>(path);
            ret.add(path_);
            return;
        }
        for(int i = 0;i < nums.length;i++){
            if(check[i] == true  || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false)){
                continue;
            }
            path.add(nums[i]);
            check[i] = true;
            dfs(nums);
            check[i] = false;
            path.remove(path.size()-1);
        }
    }

     */

}

//leetcode:76:子集
class Solution3 {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }

    public void dfs(int[] nums,int pos){
        if(pos == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }

        path.add(nums[pos]);
        dfs(nums,pos+1);
        path.remove(path.size()-1);

        dfs(nums,pos+1);
    }
}

//leetcode:1863:找出所有子集的异或总和再求和
class Solution4 {
    int ret = 0;
    int path = 0;
    public int subsetXORSum(int[] nums) {
        dfs(nums,0,path);
        return ret;
    }

    public void dfs(int[] nums,int pos,int path){
        if(pos == nums.length){
            ret += path;
            return;
        }
        path ^= nums[pos];
        dfs(nums,pos+1,path);
        path ^= nums[pos];
        dfs(nums,pos+1,path);

    }
}